package main

// Less Recently Used
// The object maintains a doubly-linked list of elements.
// When an element is accessed it is promoted to the head of the list,
//and when space is needed the element at the tail of the list (the least recently used element) is evicted.

import (
	"container/list"
	"fmt"
)

type (
	LRUCache struct {
		ll             *list.List
		cache          map[int]*list.Element
		capacity, size int
	}
	entry struct {
		key, value int
	}
)

func NewCache(capacity int) *LRUCache {
	return &LRUCache{
		ll:       list.New(),
		cache:    make(map[int]*list.Element),
		capacity: capacity,
	}
}

func (c *LRUCache) Get(key int) int {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		ety := ele.Value.(*entry)
		return ety.value
	}
	return -1
}

func (c *LRUCache) removeOldest() {
	if ele := c.ll.Back(); ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)
		c.size--
	}
}

func (c *LRUCache) Set(key, value int) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		kv.value = value
	} else {
		ele := c.ll.PushFront(&entry{key, value})
		c.cache[key] = ele
		c.size++
	}

	if c.capacity > 0 && c.size > c.capacity {
		c.removeOldest()
	}
}

func main() {

	capacity := 3
	cache := NewCache(capacity)

	cache.Set(1, 1)
	cache.Set(2, 2)
	cache.Set(3, 3)

	fmt.Println(cache.Get(1))
	fmt.Println(cache.Get(2))
	fmt.Println(cache.Get(3))
	fmt.Println("------")

	cache.Set(3, 4)
	fmt.Println(cache.Get(3))
	fmt.Println("------")

	cache.Set(4, 4)
	fmt.Println(cache.Get(1))
	fmt.Println("------")
}
